package day06;

// 全排列：回溯算法+剪枝

import java.util.ArrayList;
import java.util.TreeSet;

public class Main2 {
    // 交换
    private static void swap(char[] ch,int start,int i) {
        char tmp = ch[start];
        ch[start] = ch[i];
        ch[i] = tmp;
    }
    // 进行排列
    private static void PermutationHelper(char[] ch,int start,TreeSet<String> tmp) {
        // 同样先判断
        if(ch.length==0 || ch==null || start<0 || start>ch.length-1) {
            return ;
        }
        // 此时就要进行排列
        // 出口:需要将一条记录插入到tmp中
        if(start == ch.length-1) {
            // 此时说明已经走到了最后
            tmp.add(String.valueOf(ch));
        } else {
            // 此时就说明排列还没有结束，需要继续排列
            // 排列：交换+排列+交换回来
            // start永远指向的是还未进行交换的开头位置！！
            // 需要进行循环，使得每一个字母都有机会当开头
            // 注意i的开始是start，不是0，start是会变化的！
            for(int i=start; i<ch.length; i++) {
                swap(ch,start,i);
                PermutationHelper(ch,start+1,tmp);
                swap(ch,start,i);
            }
        }
    }
    public ArrayList<String> Permutation(String str) {
        // 存储最终结果集
        ArrayList<String> ret = new ArrayList<>();
        // 判断是否是空串
        if(str==null || str.length()==0) {
            return ret;
        }
        // 为了得到字典序，先将结果存储在TreeSet中（直接按字典序排列）
        TreeSet<String> tmp = new TreeSet<>();
        // 为了便于后续操作字符串，先转为字符数组
        char[] ch = str.toCharArray();
        // 开始进行排列:传入字符串，从0开始，先暂存到tmp中
        PermutationHelper(ch,0,tmp);
        // 然后将结果存到ret结果集中
        // addAll就是将tmp里面的每一条记录（String）都存入ret中
        // 类型也是符合的！
        ret.addAll(tmp);
        return ret;
    }
}




// 如果字符串过长就会导致不能得出正确结果
//import java.util.ArrayList;
//import java.util.Collections;
//
//public class Main2 {
//    // 交换函数
//    private static void swap(char[] chs, int i, int start) {
//        // start永远指向第一个
//        // 因为涉及到字母之间的赋值，那就转成字符数组！！
//        char ch = chs[i];
//        chs[i] = chs[start];
//        chs[start] = ch;
//    }
//
//    // 待选结果是否已经在结果集中存在，存在输出true，否则false
//    private static boolean isExist(char[] str,ArrayList<String> ret) {
//        return ret.contains(String.valueOf(str));
//    }
//
//    // 进行排列
//    private static void PermutationHelper(char[] str,int start,ArrayList<String> ret) {
//        // 首先写明出口：添加到结果集中的条件
//        // start是一直在变化的，此时就是指到了最后
//        if(start == str.length-1) {
//            // 去重
//            if(!isExist(str,ret)) { // 不存在
//                // 添加到结果集中：也是注意深浅拷贝！
//                ret.add(new String(str)); // 这里加入的时候，加入的是String类型，符合要求！
//            }
//            return;
//        }
//
//        // 此时说明不结束，继续进行排列
//        // 第一个字符（每个字母都要充当一次），使用循环来实现
//        // 交换函数，最后又交换回去了，变成了原字符串
//        for(int i=start; i<str.length; i++) {
//            swap(str,i,start); // start永远指向最开始的元素
//            // 确定首字母后，后面的都是子问题
//            // 也就是后面的都要进行之前的操作:进行排列
//            PermutationHelper(str,start+1,ret); // 注意这里的起始位置是在一开始的之后一个位置，最开始的已经确定了！
//            swap(str,i,start);
//            // 交换后又变成原来的字符串，后续进行循环的时候就只是交换一个
//        }
//
//    }
//
//    public ArrayList<String> Permutation(String str) {
//        ArrayList<String> ret = new ArrayList<>();
//
//        // 首先进行判断是否为空串
//        if(str==null || str.length()==0) {
//            return ret;
//        }
//
//        // 不是空串就进行排列
//        // 从0开始，结果保存到ret中
//        // 因为不能直接操作String类型，所以使用字符数组【当然，也可以是可变字符串形式】
//        PermutationHelper(str.toCharArray(),0,ret);
//        // 要进行一下升序排列！！（不要忘记！）
//        Collections.sort(ret);
//        return ret;
//    }
//
//    public static void main(String[] args) {
//        Main2 main2 = new Main2();
//        ArrayList<String> list = main2.Permutation("qwertyuio");
//        for (String st: list) {
//            System.out.println(st);
//        }
//
//    }
//}
